import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-21
 * Time: 20:14
 */
public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        // 点分十进制, 不符合条件直接返回
        if (s.length() < 4 || s.length() > 12){
            return res;
        }
        List<String> list = new ArrayList<>();
        dfs(s, 0, res, list);
        return res;
    }

    private void dfs(String s, int index, List<String> res, List<String> list) {
        // 必须将所有字母分成满足条件的 4 段才对
        if (index == s.length() && list.size() == 4){
            res.add(String.join(".", list));
            return;
        }
        if (index == s.length() || list.size() == 4){
            return;
        }
        int value = 0;
        // 每层三种情况, 通过循环同一处理
        for (int i = index; i < s.length(); i++) {
            // 以 0 开头
            if (s.charAt(index) == '0' && i > index){
                break;
            }
            value = value * 10 + (s.charAt(i) - '0');
            // 大于 255 直接 break
            if (value > 255){
                break;
            }
            list.add(String.valueOf(value));
            dfs(s, i + 1, res, list);
            list.remove(list.size() - 1);
        }
    }
}